package org.raymond.iworks.study.basic.algorithm.sort;

import java.util.Arrays;
import java.util.Collections;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 选择排序:
 * 从欲排序的数据中,按指定的规则选出某一个元素,再按规定交换位置后达到排序的目的
 * 思路分析:
 * 第1次从arr[0]~arr[n-1]中选取最小值,与arr[0]交换,
 * 第2次从arr[1]~arr[n-1]中选取最小值,与arr[1]交换,
 * 第3次从arr[2]~arr[n-1]中选取最小值,与arr[2]交换...
 * 第i次从arr[i-1]~arr[n-1]中选取最小值,与arr[i-1]交换,
 * 第n-1次从arr[n-2]~arr[n-1]中选取最小值,与arr[n-2]交换,
 * 总共通过n-1次交换,得到一个按排序码从小到大排列的有序序列
 *
 * init: [8, 3, 2, 1, 7, 4, 6, 5]
 * step1: [1, 3, 2, 8, 7, 4, 6, 5]
 * step2: [1, 2, 3, 8, 7, 4, 6, 5]
 * step3: [1, 2, 3, 8, 7, 4, 6, 5]
 * step4: [1, 2, 3, 4, 7, 8, 6, 5]
 * step5: [1, 2, 3, 4, 5, 8, 6, 7]
 * step6: [1, 2, 3, 4, 5, 6, 8, 7]
 * step7: [1, 2, 3, 4, 5, 6, 7, 8]
 * step8: [1, 2, 3, 4, 5, 6, 7, 8]
 *
 * 说明:
 * 1.选择排序一共有数组大小-1轮排序
 * 2.每轮排序,又是一个循环,循环的规则[代码]:
 * 2.1,先假定当前这个数是最小数
 * 2.2,然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标
 * 2.3,当遍历到数组的最后时,就得到本轮最小数和下标
 * 2.4,交换[代码]
 *
 * init: 3, 9, -1, 10, -2
 * 第1轮排序:
 * 1) 假设3最小,最小数索引为0
 * 2) 3与9比较, 3<9, 最小数不变
 * 3) 3与-1比较, 3>-1, 最小数改为-1, 最小数索引改为2
 * 4) -1与10比较, -1<10, 最小数不变
 * 5) -1与-2比较, -1>-2, 最小数改为-2, 最小数索引改为4
 * 6) 3与-2交换位置
 * 得: -2, 9, -1, 10, 3
 * []: 表示比较后落选的数
 * (): 表示比较后选中的数,此处表示最小的数
 * 1. (3), 9, -1, 10, -2
 * 2. (3), [9], -1, 10, -2
 * 3. [3], 9, (-1), 10, -2
 * 4, 9, (-1), [10], -2
 * 5. 3, 9, [-1], 10, (-2)
 * 6. (-2), 9, -1, 10, 3
 *
 * 第2轮排序:
 * 1. -2, (9), -1, 10, 3
 * 2. -2, [9], (-1), 10, 3
 * 3. -2, 9, (-1), [10], 3
 * 4. -2, 9, (-1), 10, [3]
 * 5. -2, (-1), 9, 10, 3
 *
 * 第3轮排序:
 * 1. -2, -1, (9), 10, 3
 * 2. -2, -1, (9), [10], 3
 * 3. -2, -1, [9], 10, (3)
 * 4. -2, -1, (3), 10, 9
 *
 * 第4轮排序:
 * 1. -2, -1, 3, (10), 9
 * 2. -2, -1, 3, [10], (9)
 * 3. -2, -1, 3, (9), 10
 *
 */
public class SelectSortTest {
    public static void main(String[] args) {
        int[] arr = new int[100000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*100000000);
        }
        //arr = new int[]{8,3,2,1,7,4,6,5};
        //arr = new int[]{3,9,-1,10,-2};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        long start = System.nanoTime();
        test1(arr);
        long end = System.nanoTime();
        //System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 6408237300 纳秒,约6.5秒, 100000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        start = System.nanoTime();
        jdkSort(arr);
        end = System.nanoTime();
        // post: 2560700 纳秒, 约2.5毫秒, 100000个元素的数组
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }

    public static void test1(int[] arr){
        for(int i=0; i<arr.length; i++) {
            // 比较的是整个数组除i之外的其他数据,因此要放在外层for循环里赋值
            int min=arr[i];
            int minIdx=i;
            // i不用与自身比较,也不用与历史上的i比较,因为都已经比较过了
            // i之前的数已经按顺序排好了
            //for (int j = 0; j < arr.length; j++) {
            //    if(j>i && min>arr[j]){
            for (int j = i+1; j < arr.length; j++) {
                if(min>arr[j]){
                    min = arr[j];
                    minIdx = j;
                }
                // 将数组位置i上的数与最小数互相交换
                if(j==arr.length-1){
                    arr[minIdx] = arr[i];
                    arr[i] = min;
                }
            }
            //System.out.printf("第%d轮排序后的数组:\n", i+1);
            //System.out.printf("%s\n", Arrays.toString(arr));
        }
    }

    public static void jdkSort(int[] array){
        Arrays.sort(array);
    }
}
